最长连续不重复子序列

实现

• 目的：给定一个序列，让我们找到最长连续不重复子序列
• 思路：采用双指针 $l$ 和 $r$ 来分别指向这个子序列的开头和结尾，总体思路就是：
  1. 让指针 $r$ 右移去试探
  2. 若试探的元素并没有重复，就加入子序列，并判断这个子序列长度是否大于先前记录的最大值；若重复了，就右移 $l$ 指针直到该元素（引起重复的元素）不重复为止
  3. 重复 1，2 步直到 $r$ 指针指向末尾
• 时间复杂度：$O(n)$

const int N = 100010;

// a记录这个整数序列，cnt记录当前子序列中的每一个元素的出现次数
int a[N], cnt[N];
// n记录实际整数序列的长度
int n;

int func()
{
    int maxlen = 0;
    // 用r代表子序列末尾，l代表子序列头部
    for(int l = 0, r = -1; r < n; r++, cnt[a[r]]++)
    {
        if(r < l) continue;
        while(cnt[a[r]] > 1) 
        {
            cnt[a[l]]--;
            l++;
        }
        maxlen = max(maxlen, r - l + 1);
    }
    
    return maxlen;
}